package week6;

/**
 *
 * 673. 最长递增子序列的个数
 * https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：20 ms, 在所有 Java 提交中击败了84.01% 的用户
 * 内存消耗：38.2 MB, 在所有 Java 提交中击败了23.24% 的用户
 * 通过测试用例：223 / 223
 * 炫耀一下:
 *
 *
 */
public class Week6NumberOfLongestIncreasingSubsequence {

    public int findNumberOfLIS(int[] nums) {
        int length = nums.length;
        int maxLength = 0;
        int increasingNumber = 0;
        int[] dynamicPlan = new int[length];
        int[] countArray = new int[length];
        for(int f1 = 0; f1 < length; f1++) {
            dynamicPlan[f1] = 1;
            countArray[f1] = 1;
            for(int f2 = 0; f2 < f1; f2++) {
                if(nums[f1] > nums[f2]) {
                    if(dynamicPlan[f2] + 1 > dynamicPlan[f1]) {
                        dynamicPlan[f1] = dynamicPlan[f2] + 1;
                        countArray[f1] = countArray[f2];
                    } else if(dynamicPlan[f2] + 1 == dynamicPlan[f1]) {
                        countArray[f1] += countArray[f2];
                    }
                }
            }

            if(dynamicPlan[f1] > maxLength) {
                maxLength = dynamicPlan[f1];
                increasingNumber = countArray[f1];
            } else if(dynamicPlan[f1] == maxLength) {
                increasingNumber += countArray[f1];
            }
        }

        return increasingNumber;
    }
}
